#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/11/21 14:26
# @USER    : Shengji He
# @File    : SortList.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        """
        Given the head of a linked list, return the list after sorting it in ascending order.

        Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
        Example 1:
            Input: head = [4,2,1,3]
            Output: [1,2,3,4]
        Example 2:
            Input: head = [-1,5,3,4,0]
            Output: [-1,0,3,4,5]
        Example 3:
            Input: head = []
            Output: []

        Constraints:
            - The number of nodes in the list is in the range [0, 5 * 104].
            - -10e5 <= Node.val <= 10e5

        :param head:
        :return:
        """
        def sortFunc(head: ListNode, tail: ListNode) -> ListNode:
            if not head:
                return head
            if head.next == tail:
                head.next = None
                return head
            slow = fast = head
            while fast != tail:
                slow = slow.next
                fast = fast.next
                if fast != tail:
                    fast = fast.next
            mid = slow
            return merge(sortFunc(head, mid), sortFunc(mid, tail))

        def merge(head1: ListNode, head2: ListNode) -> ListNode:
            dummy_head = ListNode(0)
            temp, temp1, temp2 = dummy_head, head1, head2
            while temp1 and temp2:
                if temp1.val <= temp2.val:
                    temp.next = temp1
                    temp1 = temp1.next
                else:
                    temp.next = temp2
                    temp2 = temp2.next
                temp = temp.next
            if temp1:
                temp.next = temp1
            if temp2:
                temp.next = temp2
            return dummy_head.next
        return sortFunc(head, None)


if __name__ == '__main__':
    S = Solution()
    head = ListNode(4)
    head.next = ListNode(2)
    head.next.next = ListNode(1)
    head.next.next.next = ListNode(3)
    output = S.sortList(head)
    print('done')
